from typing import *
from heapq import heapify, heappop, heappush
from math import inf


class Solution:

    def minimumJumps(self, forbidden: List[int], a: int, b: int,
                     x: int) -> int:
        r = 6000
        s = set(forbidden)
        pos = [False] * r
        pos[0] = True
        q = []
        heappush(q, (0, 0, 0))
        while q:
            c, p, t = heappop(q)
            if p == x:
                return c
            if p + a < r and not pos[p + a] and p + a not in s:
                pos[p + a] = True
                heappush(q, (c + 1, p + a, 0))
            if t == 0 and p - b >= 0 and not pos[p - b] and p - b not in s:
                pos[p - b] = True
                heappush(q, (c + 1, p - b, 1))

        return -1


s = Solution()
# print(s.minimumJumps([14,4,18,1,15],3,15,9))
print(
    s.minimumJumps([
        162, 118, 178, 152, 167, 100, 40, 74, 199, 186, 26, 73, 200, 127, 30,
        124, 193, 84, 184, 36, 103, 149, 153, 9, 54, 154, 133, 95, 45, 198, 79,
        157, 64, 122, 59, 71, 48, 177, 82, 35, 14, 176, 16, 108, 111, 6, 168,
        31, 134, 164, 136, 72, 98
    ], 29, 98, 80))
